package com.ljy.my_study.leetcode.组合总和;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/1/12 11:57
 */
public class TestMain {

//    给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
//    candidates 中的数字可以无限制重复被选取。
//
//    说明：
//
//    所有数字（包括 target）都是正整数。
//    解集不能包含重复的组合。 
//    示例 1：
//
//    输入：candidates = [2,3,6,7], target = 7,
//    所求解集为：
//            [
//            [7],
//            [2,2,3]
//            ]
//    示例 2：
//
//    输入：candidates = [2,3,5], target = 8,
//    所求解集为：
//            [
//              [2,2,2,2],
//              [2,3,3],
//              [3,5]
//            ]
//             
//
//    提示：
//
//            1 <= candidates.length <= 30
//            1 <= candidates[i] <= 200
//    candidate 中的每个元素都是独一无二的。
//            1 <= target <= 500
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/combination-sum

    public static void main(String[] args) {
        int[] candidates=null;
        int target=1;
        System.out.println(new TestMain().combinationSum(candidates,target));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result=new ArrayList<>();
        if(candidates==null){
            return result;
        }
        Arrays.sort(candidates);
        for(int i=0;i<candidates.length;i++){
            int value=candidates[i];
            if(value>target){
                break;
            }
            List<Integer> list=new ArrayList<>();
            list.add(value);
            if(value==target){
                result.add(list);
                break;
            }
            doCombinate(result,list,candidates,target-value,i);
        }

        return result;
    }

    private void doCombinate(List<List<Integer>> result,List<Integer> list,int[] candidates,int target,int index){
        for(int i=index;i<candidates.length;i++){
            List<Integer> nextList=new ArrayList<>(list);
            int value=candidates[i];
            if(target-value==0){
                nextList.add(value);
                result.add(nextList);
                return;
            }else if(target-value>0){
                nextList.add(value);
                doCombinate(result,nextList,candidates,target-value,i);
            }else{
                return;
            }
        }
    }
}
